/*
 * Created by Jesse Phillips
 * Created on Jan 26, 2006
 */
/**
 * Manager of Nodes which contain the elements of the LinkedList.
 * It has three constructers: default, one that takes a data element,
 * and one that takes an array. Elements will be added in order if they
 * are found to be Comparable otherwise it will be appended to the end.
 * 
 * @author Jesse Phillips
 * @see "No barrowed code."
 */
public class LinkedList<E> {
	// Master Node, though not counted as part of the list, this Node
	//will point to the begining(getNext()) and the end(getPrev()).
	//Also it will contain an Integer of how many nodes are in the list.
	private Node<Integer> master;
	private Node masterCur;
	
	/**
	 * Default constructer, builds an empty master Node.
	 */
	public LinkedList() {
		master = new Node<Integer>(0);
		masterCur = master;
	}
	
	/**
	 * Constructer that takes a data element.
	 * 
	 * @param data Object that is stored in the Node.
	 */
	public LinkedList(E data) {
		Node add = new Node<E>(data);
		master = new Node<Integer>(1, add, add);
		masterCur = master;
	}
	
	/**
	 * Constructer that builds a linked list out of an array.
	 * Items will be sorted if they extend comparable.
	 * 
	 * @param data
	 */
	public LinkedList(E[] data) {
		master = new Node<Integer>();
		masterCur = master;
		
		for(int i=0; i<data.length; i++)		
				add(data[i]);
	}
	
	/**
	 * Creates the Node at the end of the list.
	 * 
	 * @param data What is to be stored in the Node.
	 * @return void
	 */
	public void addEnd(E data) {
/*ans bl*/
		master.setElement(master.getElement()+1);
		if(isEmpty()) {
			buildEmpty(data);
		}else {
			master.setPrev(new Node<E>(data, null, master.getPrev()));
		}
/*ans ab*/
	}
	
	/**
	 * Creates the Node at the beginning of the list.
	 * 
	 * @param data What is to be stored in the Node.
	 * @return void
	 */
	public void addBeginning(E data) {
		master.setElement(master.getElement()+1);
		if(isEmpty()) {
			buildEmpty(data);
		}else {
			master.setNext(new Node<E>(data, master.getNext(), null));
		}
	}
	
	/**
	 * Adds the element in sorted order if comparable and throws
	 * an exceptions if it is not.
	 * 
	 * @param data What is to be stored in the Node.
	 * @throws Exception States that it cannot sort because it is not Comparable.
	 * @return void
	 */
	public void add(E data) {
/*ans bl*/
		if(data instanceof Comparable) {
			Comparable element = (Comparable) data;
			master.setElement(master.getElement()+1);
			if(isEmpty()) {
				buildEmpty(data);
			}else {
				findInsertion(master.getNext(), element);
			}
		}
		else {
			addEnd(data);
			System.out.println("Cannot sort non-Comparable!\n" +
					"Added to the end of list");
		}
/*ans ab*/
	}
	
	/**
	 * Removes all Nodes containg 'value' from the list.
	 * 
	 * @param value What should be removed.
	 * @return An int of how many were removed.
	 */
	public int removeAll(E value) {
		int destroyed = kill(value, master.getNext());
		master.setElement(master.getElement() - destroyed);
		return destroyed;
	}
	
	/**
	 * Empties the linkList.
	 * 
	 * @return void
	 */
	public void removeAll() {
		master.setElement(0);
		master.setNext(null);
		master.setPrev(null);
	}

	/**
	 * Tells if there is any Nodes in the LinkedList.
	 * 
	 * @return A boolean value of wheather it is empty or not.
	 */
	public boolean isEmpty() {
		if(master.getNext() == null) return true;
		else return false;
	}
	
	/**
	 * @return A String of all elements in the Linked List.
	 * @see java.lang.Object#toString()
	 */
	public String toString() {
		return print(master.getNext(), 1, 1);
	}
	
	/**
	 * Prints LinkedList in reverse.
	 * 
	 * @return String of all elements in the LinkedList.
	 */
	public String stringTo() {
		return printReverse(master.getPrev());
	}
	
	/**
	 * Print every Nth term in the list.
	 * 
	 * @param N How many are skipped.
	 * @return A String ove every Nth Node.
	 */
	public String everyNth(int N) {
		return print(master.getNext(), N, 1);
	}
	
	/**
	 * Returns the next element in the list of type <E>
	 * 
	 * @return The element <E> that appears next in the list.
	 */
	public E next() {
		masterCur = masterCur.getNext();
		return (E) masterCur.getElement();
	}
	
	/**
	 * Tells if there is another element that can be returned.
	 * 
	 * @return A boolean of whether there is another element in the list. 
	 */
	public boolean hasNext() {
		if(masterCur.getNext() != null) return true;
		else return false;
	}
	
	/**
	 * Returns a String of the Nth number in the list.
	 * 
	 * @param cur Current Node to print.
	 * @param N Skip N nodes each time.
	 * @param count how for down the list.
	 * @return A String of the list contests.
	 */
	private String print(Node cur, int N, int count) {
/*ans bl*/
		if(isEmpty()) return "";
		else if(cur == null)
			return "";
		else
			return (count%N==0?(cur.toString()+"\n") 
					: "")
					+ print(cur.getNext(), N, count+1);
/*ans ab*/
	}
	
	/**
	 * Returns a String of the List contents in reverse.
	 * 
	 * @param cur Current Node to be print
	 * @return A String of the list contests in reverse.
	 */
	private String printReverse(Node cur) {
		if(isEmpty())
			return "";
		else if(cur.getPrev() == null)
			return cur.toString();
		else
			return cur.toString() + "\n" + printReverse(cur.getPrev());
	}
	
	/**
	 * A recursive function that finds and inserts a Comparable element
	 * to the list of nodes. Used by the public method add().
	 * 
	 * @param cur The Current Node.
	 * @param element What is to be added.
	 */
	private void findInsertion(Node cur, Comparable element) {
		if(cur == null) return ;
		if(element.compareTo(cur.getElement()) <= 0)
			if(cur.getPrev() == null) {
				Node newNode = new Node<E>((E)element, cur, cur.getPrev());
				master.setNext(newNode);
				cur.setPrev(newNode);
			}else {
				Node newNode = new Node((E)element, cur, cur.getPrev());
				newNode.getPrev().setNext(newNode);
				newNode.getNext().setPrev(newNode);
			}
		else {
			if(cur.getNext() == null) {
				master.setPrev(new Node((E)element, cur.getNext(), cur));
				cur.setNext(master.getPrev());
			}else
				findInsertion(cur.getNext(), element);
		}
	}
	
	/**
	 * Recursive method used by the public method remove(<E>)
	 * that finds and removes all Nodes containing <E>.
	 * 
	 * @param value What is to be removed.
	 * @param cur The current Node being looked at.
	 * @return Number of Nodes removed.
	 */
	private int kill(E value, Node cur) {
		if(cur == null) return 0;
		if(((Comparable)cur.getElement()).compareTo(value) == 0) {
			if(cur.getNext() == null) {
				cur.getPrev().setNext(cur.getNext());
				master.setPrev(cur.getPrev());
				return 1;
			}else if(cur.getPrev() == null) {
				cur.getNext().setPrev(cur.getPrev());
				master.setNext(cur.getNext());
				return 1 + kill(value, cur.getNext());
			}else {
				cur.getNext().setPrev(cur.getPrev());
				cur.getPrev().setNext(cur.getNext());
				return 1 + kill(value, cur.getNext());
			}
		}else
			return kill(value, cur.getNext());
	}
	
	/**
	 * Adds a Node to the list when the list is already empty.
	 * 
	 * @param data What the Node is to store.
	 * @return void
	 */
	private void buildEmpty(E data) {
		Node node = new Node<E>(data);
		master.setNext(node);
		master.setPrev(node);
	}
}
